Microcircuit devices have become commonly used in a variety of products, from automobiles to microwaves to personal computers. As the importance of these devices grows, manufacturers continue to improve these devices. Each year, for example, microcircuit device manufacturers develop new techniques that allow microcircuit devices, such as programmable microprocessors, to be more complex and yet still smaller in size.
As microcircuit devices become more complex, they also become more difficult to design and test. A conventional microcircuit device, for example, may have many millions of connections, and each connection may cause the microcircuit to operate incorrectly or even fail if the connection is not properly designated. Not only must the connections be properly designated, but the time required for each circuit structure to process or transmit a signal must fall within a desired time constraint. If a circuit structure, such as a transistor gate, takes too long to process a signal, then another circuit structure may not receive the signal in time to operate properly. Similarly, if a circuit structure, such as a wiring line, takes too long to transmit a signal, then another circuit structure may not receive the signal in time to perform its intended task.
Accordingly, when designing or testing a microcircuit, it is often important to consider the timing characteristics of various structures in the circuit. Final timing verification of a circuit design is normally performed using extracted parasitics. In order to be efficient, these timing verification techniques require compact circuit interconnect models. As a result, model order reduction of RC and RCLM networks has been a vigorous area of research during the last decade. Reduction of RC and RCLM networks using moment matching techniques, such as asymptotic waveform evaluation, has been a dominant theme. An example of this technique is discussed in “Asymptotic Waveform Evaluation For Timing Analysis,” by L. Rohrer and L. Pillage, IEEE TCAD, Vol. 9, pp. 352-366, 1990.
Other model order reduction techniques are described in “Efficient Linear Circuit Analysis by Pade Approximation via the Lanezos Process,” by P. Feldmann and R. W. Freund, Euro-DAC 1994, pp. 170-75, “A Coordinate-Transformed Arnoldi Algorithm for Generating Guaranteed Stable Reduced-Order Models of RLC Circuits,” by M. Silveira, M. Kamon, I. Elfadel and J. White, DAC 1996, pp. 288-94, and “Stable and Efficient Reduction of substrate Model Networks Using Congruence Transforms,” by K. Kerns, I. Wemple. A. Yang, ICCAD 1995, pp. 207-14. These techniques improve numerical conditioning, while the congruence transformations solve stability problems. The culmination in this evolution is Krylov subspace projection methods like PRMA, which is described in “PRIMA: Passive Reduced-order Interconnect Macromodeling Algorithm,” by A. Odabasioglu, M. Celik, L. Pileggi, DAC 1997, pp. 5865.
A different approach to analyzing the timing characteristics of a circuit design, however, employs a realizable circuit rather than an abstract model. With these analysis techniques, the realizable circuit is created by abridging the original circuit. The smaller realizable circuit is created from local circuit transformations on the original circuit, by which some nodes or branches of the original circuit are eliminated or modified, and other nodes or branches may be introduced. While the resulting circuit is simpler than the original circuit, it will approximately replicate certain behaviors of the original circuit. Thus, the timing of the reduced circuit can be analyzed instead of the original circuit, and more efficiently.
Various approaches to this method are described in, for example, “Extracting Simple but Accurate RC models for VLSI Interconnect,” by A. van Genderen and N. van der Meijs, Proc. IEEE Symp. Circuits and Systems, 1988, pp. 2351-54, “DARSI: RC Data Reduction,” by P. Vanoostende, P. Six, and H. De Man, IEEE TCAD, vol. 10, 1991, pp. 493-500, “Extracting Circuit Models for Large RC Interconnections that are Accurate up to a Predefined Signal Frequency,” by P. Elias and N. van der Meijs, DAC 1996, pp. 764-69, “TICER: Realizable Reduction of Extracted RC Circuits,” by B. Sheehan, ICCAD 1999, pp. 200-03, and B. Sheehan, “ENOR: Model Order Reduction of RLC Circuits Using Nodal Equations for Efficient Factorization,” DAC 1999.